// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.IO;
using System.Threading;
using System.Globalization;

namespace UGent.Tsp
{
    /// <summary>
    /// Represents a single Markov Chain.
    /// </summary>
    [Serializable()]
    public class MarkovChain : MarshalByRefObject
    {
        private const int LogInterval = 750000;
        private const int VerifyResultInterval = 10000;
        
        public MarkovChain()
        {
            Reset();
        }

        [NonSerialized()]
        private Route route;
        private ISwapper swapper;
        private double beta;
        private double length;
        private bool running;
        private Thread thread;
        private Random random;
        private Results results;
        private Distribution distribution;
        private Transitions transitions;
        private AlgorithmType algorithmType;
        private double upperLimit;
        private bool useUpperLimit;
        private int correlationCount = Results.DefaultCorrelationCount;
        private int histogramNumberOfBins = Results.DefaultHistogramNumberOfBins;
        private double histogramLower = 0.0;
        private double histogramUpper = 100.0;
        private bool histogramLowerExtended = true;
        private bool histogramUpperExtended = true;
        private int[] optimalRoute;
        private double optimalRouteLength = double.MaxValue;
        private double maximalRouteLength = double.MaxValue;
        private int chainId;
        private bool biasForLowEnergy;
        private double f;
        
        /// <summary>
        /// Specifies the status of the Markov Chain.
        /// </summary>
        public enum Status
        {
            /// <summary>
            /// The Markov Chain is currently running.
            /// </summary>
            Running,

            /// <summary>
            /// The Markov Chain has recieved a stop request, and is currently stopping.
            /// </summary>
            Stopping,

            /// <summary>
            /// The Markov Chain is not running.
            /// </summary>
            Stopped
        }

        /// <summary>
        /// Gets or sets the <see cref="Algorithm"/> to use.
        /// </summary>
        public AlgorithmType AlgorithmType
        {
            get { return algorithmType; }
            set { algorithmType = value; }
        }

        public bool BiasForLowEnergy
        {
            get { return biasForLowEnergy; }
            set { biasForLowEnergy = value; }
        }

        public int CorrelationCount
        {
            get { return correlationCount; }
            set { correlationCount = value; }
        }

        public int HistogramNumberOfBins
        {
            get { return histogramNumberOfBins; }
            set { histogramNumberOfBins = value; }
        }

        public double HistogramLower
        {
            get { return histogramLower; }
            set { histogramLower = value; }
        }

        public double HistogramUpper
        {
            get { return histogramUpper; }
            set { histogramUpper = value; }
        }

        public bool HistogramLowerExtended
        {
            get { return histogramLowerExtended; }
            set { histogramLowerExtended = value; }
        }

        public bool HistogramUpperExtended
        {
            get { return histogramUpperExtended; }
            set { histogramUpperExtended = value; }
        }

        public int ChainId
        {
            get { return chainId; }
            set 
            { 
                this.random = new Random(value);
                chainId = value; 
            }
        }
        
        public double UpperLimit
        {
            get { return this.upperLimit; }
            set { this.upperLimit = value; }
        }
        
        public bool UseUpperLimit
        {
            get { return this.useUpperLimit; }
            set { this.useUpperLimit = value; }
        }
        
        public double WangLandauParameter
        {
            get { return f; }
            set { f = value; }
        }
        
        /// <summary>
        /// Gets the status of the Markov Chain.
        /// </summary>
        /// <returns>The status of the Markov Chain.</returns>
        public Status GetStatus()
        {
            if (running)
                return Status.Running;
            else if (thread != null && thread.IsAlive)
                return Status.Stopping;
            else
                return Status.Stopped;
        }

        /// <summary>
        /// Resets the Markov Chain.
        /// </summary>
        public void Reset()
        {
            Console.WriteLine("MarkovChain.Reset()");
            this.random = new Random();
            this.route = null;
            this.swapper = null;
            this.beta = 0;
            this.length = 0;

            // This should stop the thread
            this.running = false;

            while (this.thread != null && this.thread.IsAlive)
                Thread.Sleep(100);

            this.thread = null;
            this.results = null;

            // Default to a random walk in energy space.
            this.algorithmType = AlgorithmType.Metropolis;
            this.beta = 0;
            this.distribution = null;
        }

        /// <summary>
        /// Sets the <see cref="Map"/> to be used by the Markov Chain.
        /// </summary>
        /// <param name="map">The <see cref="Map"/> to be used by the Markov Chain.</param>
        public void SetMap(Map map)
        {
            Console.WriteLine("MarkovChain.SetMap()");

            if (map == null)
            {
                this.route = null;
                this.length = 0;
            }
            else
            {
                this.route = new Route(map);
                this.length = route.GetLength();
            }
        }

        /// <summary>
        /// Sets the <see cref="ISwapper"/> to be used by the Markov Chain.
        /// </summary>
        /// <param name="type">The <see cref="Type"/> of the swapper.</param>
        /// <param name="count">A parameter for the swapper.</param>
        public void SetSwapper(Type type, int count)
        {
            Console.WriteLine("MarkovChain.SetSwapper()");
            if (type != null)
                this.swapper = Swappers.Create(type, route, count);
            else
                this.swapper = null;
        }

        /// <summary>
        /// Sets the value of beta to use when doing Metropolis sampling.
        /// </summary>
        /// <param name="value">The value of beta to use when doing Metropolis sampling.</param>
        public void SetBeta(double value)
        {
            Console.WriteLine("MarkovChain.SetBeta()");
            this.beta = value;
        }

        /// <summary>
        /// Sets the distribution to use when doing Metropolis-Hastings sampling.
        /// </summary>
        /// <param name="value">The distribution to use when doing Metropolis-Hastings sampling.</param>
        public void SetDistribution(Distribution value)
        {
            Console.WriteLine("MarkovChain.SetDistribution()");
            this.distribution = value;
        }

        public void SetTransitionMatrix(Transitions value)
        {
            Console.WriteLine("MarkovChain.SetTransitionMatrix()");
            this.transitions = value;
        }
        
        /// <summary>
        /// Starts the Markov Chain..
        /// </summary>
        public void Start()
        {
            Console.WriteLine("Started Markov Chain");
            this.running = true;
            this.results = new Results(correlationCount, histogramNumberOfBins, histogramLower, histogramLowerExtended, histogramUpper, histogramUpperExtended);

            // This is the first "move" that is done, it is always accepted;
            this.results.Add(length, TransitionType.Success);
            this.thread = new Thread(new ThreadStart(Run));
            this.thread.Start();
            Console.WriteLine("Markov Chain started. this.Results.Count = {0}. Algorithm: {1}", this.results.Count, this.AlgorithmType);
        }

        public void Resume()
        {
            Console.WriteLine("Resuming Markov Chain");
            this.running = true;
            this.thread = new Thread(new ThreadStart(Run));
            this.thread.Start();
            Console.WriteLine("Markov Chain started. this.Results.Count = {0}. Algorithm: {1}", this.results.Count, this.AlgorithmType);            
        }
        
        // Worker thread that runs the simulation
        private void Run()
        {
            Console.WriteLine("Markov Chain started. this.Results.Count = {0}. Algorithm: {1}", this.results.Count, this.AlgorithmType);

            try
            {
                double delta;
                double newLength;
                double acceptance;
                double probability;
                double newProbability;

                while (running)
                {
                    swapper.Generate();
                    delta = swapper.GetDelta();
                    newLength = length + delta;

                    if(this.useUpperLimit && newLength > this.maximalRouteLength)
                    {
                        results.Add(newLength, TransitionType.Failed);
                    }
                    else if(biasForLowEnergy && delta < 0)
                    {
                        swapper.Do();
                        length = newLength;
                        results.Add(length, TransitionType.Success);
                    }
                    else
                    {
                        acceptance = random.NextDouble();
                        
                        switch (AlgorithmType)
                        {
                            case AlgorithmType.Metropolis:
                                if (Math.Exp(-1.0 * delta * beta) > acceptance)
                                {
                                    swapper.Do();
                                    length = newLength;
                                    results.Add(length, TransitionType.Success);
                                }
                                else
                                {
                                    results.Add(newLength, TransitionType.Failed);
                                }
                                break;

                            case AlgorithmType.MetropolisHastings:
                                probability = distribution.GetValue(length);
                                newProbability = distribution.GetValue(newLength);
                                
                                if (newProbability / probability > acceptance)
                                {
                                    swapper.Do();
                                    length = newLength;
                                    results.Add(length, TransitionType.Success);
                                }
                                else
                                {
                                    results.Add(newLength, TransitionType.Failed);
                                }
                                break;
                                
                            case AlgorithmType.Transitions:
                                probability = transitions.TransitionMatrix[transitions.GetBinIndex(length), transitions.GetBinIndex(newLength)];
                                newProbability = transitions.TransitionMatrix[transitions.GetBinIndex(newLength), transitions.GetBinIndex(length)];
                                
                                // If probabilty == 0, this means that this step has never been done before. Hence, always
                                // accept it!
                                if (probability == 0 || newProbability / probability > acceptance)
                                {
                                    swapper.Do();
                                    length = newLength;
                                    results.Add(length, TransitionType.Success);
                                }
                                else
                                {
                                    results.Add(newLength, TransitionType.Failed);
                                }
                                break;
                                
                            case AlgorithmType.WangLandau:
                                int index = results.Transitions.GetBinIndex(length);
                                int newIndex = results.Transitions.GetBinIndex(newLength);
                                
                                // Calculate the log probability, assuming the distribution is at
                                // the log probability.
                                probability =distribution[index] + Math.Log(f) * results.Transitions.Histogram[index];
                                newProbability = distribution[newIndex] + Math.Log(f) * results.Transitions.Histogram[newIndex];
                                
                                // Actually, sample according to the *inverse*
                                if (probability - newProbability > Math.Log(acceptance))
                                {
                                    swapper.Do();
                                    length = newLength;
                                    results.Add(length, TransitionType.Success);
                                }
                                else
                                {
                                    results.Add(newLength, TransitionType.Failed);
                                }
                                break;
                                
                            default:
                                throw new NotSupportedException();
                        }
                        
                        if(length < optimalRouteLength)
                        {
                            optimalRouteLength = length;
                            maximalRouteLength = length * upperLimit;
                            Console.WriteLine("Optimal length: {0}. Maximal length: {1}", optimalRouteLength, maximalRouteLength);
                            optimalRoute = (int[])route.GetRoute().Clone();
                            
                            using(FileStream stream = new FileStream("OptimumRoute" + chainId.ToString() + ".txt", FileMode.Create))
                            using(StreamWriter writer = new StreamWriter(stream))
                            {
                                for(int i = 0; i < optimalRoute.Length; i++)
                                    writer.WriteLine(string.Format(CultureInfo.InvariantCulture, "{0}, {1}", i, optimalRoute[i]));
                            }
                        }
                    }
                    
                    // Do a check for the simulation length. A glitch in the swap class may cause the length
                    // to be invalid. Therefore, we always reset the length after a fixed value of steps.
                    // If the difference between the length logged by the Markov chain and the real length is
                    // big enough, something went wrong. We reset the optimal route in that case, because it is
                    // quite likely unreliable.
                    if(results.Count % VerifyResultInterval == 0)
                    {
                        double realLength = route.GetLength();
                        if(realLength < length - 0.1)
                        {
                            optimalRouteLength = double.MaxValue;
                            maximalRouteLength = double.MaxValue;
                            Console.WriteLine("Length error;");
                        }
                        length = route.GetLength();
                    }
                    
                    if(results.Count % LogInterval == 0)
                    {
                        using(StreamWriter writer = new StreamWriter("OptimumRoute" + chainId.ToString() + ".dat", true))
                        {
                            writer.WriteLine(string.Format(CultureInfo.InvariantCulture, "{0}", length));
                        }
                    }
                }
            }
            catch(Exception ex)
            {
                File.WriteAllText("ErrorLog" + chainId.ToString() + ".txt", ex.ToString());
                throw;
            }
            
            Console.WriteLine("Markov Chain stopped.");
        }

        /// <summary>
        /// Stops the Markov Chain.
        /// </summary>
        public void Stop()
        {
            Console.WriteLine("Stopping Markov Chain");
            this.running = false;
        }

        /// <summary>
        /// Estimates the autocorrelation time of this Markov Chain.
        /// </summary>
        /// <returns>The estimated autocorrelation time of this Markov Chain.</returns>
        public double GetAutocorrelationTime()
        {
            return results.GetAutocorrelationTime();
        }

        /// <summary>
        /// Gets the <see cref="Results"/> of this Markov Chain.
        /// </summary>
        /// <returns>The <see cref="Results"/> of this Markov Chain.</returns>
        public Results GetResults()
        {
            return results.Clone();
        }

        /// <summary>
        /// Gets the progress of this Markov Chain.
        /// </summary>
        /// <returns>The number of steps in this Markov Chain.</returns>
        public long GetProgress()
        {
            Console.WriteLine("MarkovChain.GetProgress()");
            return results.Count;
        }
    }
}
